package jjn.carl.binary_tree;

import commons.BinaryTreeHelper;
import commons.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jiang Jining
 * @since 2023-07-15 21:53
 */
public class LeetCode257 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        buildPath(root, new ArrayList<>(), result);
        return result;
    }
    
    private void buildPath(TreeNode node, List<Integer> res, List<String> result) {
        res.add(node.val);
        if (node.left == null && node.right == null) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < res.size(); i++) {
                Integer path = res.get(i);
                stringBuilder.append(path);
                if (i < res.size() - 1) {
                    stringBuilder.append("->");
                }
            }
            result.add(stringBuilder.toString());
            return;
        }
        if (node.left != null) {
            buildPath(node.left, res, result);
            res.remove(res.size() - 1);
        }
        if (node.right != null) {
            buildPath(node.right, res, result);
            res.remove(res.size() - 1);
        }
    }
    
    public static void main(String[] args) {
        List<Integer> input = new ArrayList<>();
        input.addAll(List.of(1, 2, 3));
        input.add(null);
        input.add(5);
        TreeNode root = BinaryTreeHelper.buildTree(input);
        List<String> binaryTreePaths = new LeetCode257().binaryTreePaths(root);
        System.out.println("binaryTreePaths = " + binaryTreePaths);
    }
}
